#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/8/11 16:41
# ===========================================
#       题目名称： 85. 最大矩形
#       题目地址： https://leetcode.cn/problems/maximal-rectangle
#       题目描述： https://note.youdao.com/s/LWYgPSzT
# ===========================================


class Solution:
    """
        给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，
    并返回其面积。
    """

    def maximalRectangle(self, matrix):
        """
            实现思路: 根据84. 柱状图中最大的矩形 求出最大矩形
        """
        max_area = 0
        level = 1  # 层
        while level <= len(matrix):
            heights = [0 for _ in range(len(matrix[0]))]             # 全部定为0
            heights_flag = [True for _ in range(len(matrix[0]))]     # 标记
            for m in reversed(range(level)):
                for n in range(len(matrix[m])):
                    if matrix[m][n] == "1":
                        if heights_flag[n]:
                            heights[n] += 1
                    else:
                        heights_flag[n] = False

            max_area = max(max_area, self.largestRectangleArea(heights))
            level += 1
        return max_area

    def largestRectangleArea(self, heights):
        """
            以空间换时间
        """
        max_area = 0
        heights = [0] + heights + [0]
        stack = []
        for i in range(len(heights)):
            # print(stack)
            while stack and heights[stack[-1]] > heights[i]:
                top = stack.pop()
                max_area = max(max_area, heights[top] * (i - stack[-1] - 1))
            stack.append(i)
        return max_area


if __name__ == '__main__':
    s = Solution()
    # 6
    print("6 =>", s.maximalRectangle(matrix=[["1", "0", "1", "0", "0"], ["1", "0", "1", "1", "1"], ["1", "1", "1", "1", "1"], ["1", "0", "0", "1", "0"]]))
    # 0
    print("0 => ", s.maximalRectangle(matrix=[]))
    # 0
    print("0 => ", s.maximalRectangle(matrix=[["0"]]))
    # 1
    print("1 => ", s.maximalRectangle(matrix=[["1"]]))
    # 0
    print("0 => ", s.maximalRectangle(matrix=[["0", "0"]]))
    # 1
    print("1 => ", s.maximalRectangle(matrix=[["0", "1"], ["1", "0"]]))
    # 6
    print("6 =>", s.maximalRectangle([
        ["1", "0", "1", "1", "1"],
        ["0", "1", "0", "1", "0"],
        ["1", "1", "0", "1", "1"],
        ["1", "1", "0", "1", "1"],
        ["0", "1", "1", "1", "1"]]))
